In the remaining part of this document, we shall strive more particularly to describe the existing issues and questions that were faced by the inventors of the present application in a context of network encoding in a wireless mesh network. An embodiment of the invention is of course not limited to this particular context of application but is worthwhile in all cases of network encoding adapted to the transmission, through relay nodes, of data packets from one or more source nodes to destination nodes in a mesh communication network.
A wireless mesh communication network consists of a set S of M source nodes and a set Dt of N destinations nodes. The transmissions concerned are known as multicast transmission, i.e. each data packet sent by a source node is addressed to all the destination nodes of Dt. The other nodes are relay nodes, used to retransmit the source packets sent by the source nodes. The topology of the network is assumed to be known, i.e. all the radio qualities (such as the radio power received) between two communicating nodes are known.
Relay nodes classically have the function of retransmitting one of the packets that they have received at input (routing function). In the context of network encoding, these relay nodes have a new functionality: they have the capacity to send a resultant packet which is a combination of the packets received at input.
The concept of network encoding was introduced by R. Ahlswede and al (see: R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung “Network Information Flow” I.E.E.E. Transactions on Information Theory Vol 46, No 4, pp 1204-1216, July 2000) and very soon, many other articles were published demonstrating the contribution made by this new concept, especially in terms of bandwidth gain and use of network capacity.
The following is commonly called a network encoding scheme:                all the combinant relay nodes of the packets at input to generate a combined packet called a resultant packet;        for these combinant relay packets, the input packets to be combined among all the packets received;        each input packet to be combined has an associated coefficient in Fq.        
These combinant relay nodes and these packets (they are included in the network encoding scheme) are considered to be payload elements while the others are considered to be redundant. The destination nodes then receive a plurality of packets which are a linear combination of the source packets (packets sent by the source nodes). From these received packets, they compute a decoding matrix which will enable the decoding of the source packets (i.e. the building of the source packets reconstituted from received packets).
In the prior art, there are mainly two approaches to building a network encoding scheme as a function of knowledge or lack of knowledge of the initial topology of the network.
In the prior art, there are chiefly two approaches to building a network encoding scheme as a function of the knowledge or lack of knowledge of the initial topology of the network:                For a known topology, a first deterministic scheme for building coefficients based on a matrix approach is given in the following article: R. Koetter, M. Médard, “An Algebraic Approach to Network Coding” ACM transactions on Networking, Vol 11, No 5, October 2003”. The network encoding scheme obtained according to this first approach is called a “deterministic encoding scheme”;        For an unknown topology, a construction on the fly of the randomly drawn coefficients is given by: Michelle Effros, Tracey Ho, David Karger, Ralf Koetter, Muriel Medard, in “Randomized distributed network coding” (cf U.S. patent application; 20050152391). The network encoding scheme obtained according to this second approach is called a “random encoding scheme”.        
In the first approach, the coefficients are computed once and for all at the start of the system and therefore during the lifetime of the system. The destination nodes and the relay nodes entail low-cost operations because they know exactly what they are going to receive and transmit.
In the second approach, the relay nodes randomly draw the coefficients of the resultant packet to be generated. This requires an additional processing time. Furthermore, they are obliged to send the randomly drawn coefficients in the resultant packet so that the other nodes, and more especially the destination nodes, know the linear combinations for decoding. This signaling (the sending of the coefficients) is especially great as the Galois field is great (each coefficient will be encoded on a greater number of bits) and this amounts to as much lost bandwidth. Now in this second approach, the greater the Galois field, the greater are the chances of success in the decoding of the source packets. This means there must be a necessary compromise between the size of the field and the bandwidth used for the signaling.
At present, as far as the inventors know, there is no method which can be used to:                enable a simple and automatic way of determining, by means of a deterministic approach, the nodes that can participate in network encoding in a meshed network as a function of communications condition; and        optimally allocating the bandwidth in the meshed network applying the network encoding.        